//
// Created by madison on 2022/7/17.
//

#include "unordered_set"

using namespace std;


/**
 * Definition for singly-linked list.
 **/
struct ListNode {
    int val;
    ListNode *next;

    ListNode(int x) : val(x), next(nullptr) {}

    ListNode() : val(0), next(nullptr) {}

    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    // 方法一：哈希表
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode *> seen;
        while (head != nullptr) {
            if (seen.count(head)) {
                return true;
            }
            seen.insert(head);
            head = head->next;
        }
        return false;
    }

    // 方法二：快慢指针
    bool hasCycle1(ListNode *head) {
        if (head == nullptr || head->next == nullptr) {
            return false;
        }
        ListNode *slow = head;
        ListNode *fast = head->next;
        while (slow != fast) {
            if (fast == nullptr || fast->next == nullptr) {
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        return true;
    }
};

int main() {
    ListNode *node4 = new ListNode(1);
    ListNode *node3 = new ListNode(2, node4);
    ListNode *node2 = new ListNode(1, node3);
    ListNode *node1 = new ListNode(2, node2);
    ListNode *head = new ListNode(1, node1);
    node4->next = node2;
    ListNode *temp = head;
//    while (temp) {
//        printf("%d\t", temp->val);
//        temp = temp->next;
//    }
    printf("\n");


    Solution solution;
    printf("%d", solution.hasCycle1(head));
    return 0;
}